package com.cheung.leetcode.backtrack;

import org.junit.jupiter.api.Test;

import java.util.List;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.backtrack
 * @Author :  cheungming
 * @CreateTime : 2024-05-25 09:32:08
 * @Description : 分割回文串
 * @Version : 1.0
 */
public class Code131Test {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new java.util.ArrayList<>();
        backtrack(s, 0, new java.util.ArrayList<>(), res);
        return res;
    }

    public void backtrack(String s, int start, List<String> path, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new java.util.ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                path.add(s.substring(start, i + 1));
                backtrack(s, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int i) {
        String string = s.substring(start, i + 1);
        for (int j = 0; j < string.length() / 2; j++) {
            if (string.charAt(j) != string.charAt(string.length() - 1 - j)) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void test1() {
        String s = "aab";
        List<List<String>> res = partition(s);
        assert res.equals(List.of(List.of("a", "a", "b"), List.of("aa", "b")));
    }

    @Test
    public void test2() {
        String s = "a";
        List<List<String>> res = partition(s);
        assert res.equals(List.of(List.of("a")));
    }
}
